package com.dyz.leetcode._14_binarySearchTree;

import com.dyz.leetcode.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class _105_buildTree {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> idMap = new HashMap<>();
        for(int i =0; i<inorder.length; i++){
            idMap.put(inorder[i], i);
        }

        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        int inorderIndex = 0;
        for(int i=1; i<preorder.length; i++){
            int childVal = preorder[i];
            TreeNode parentNode = stack.peek();
            if(idMap.get(childVal)<idMap.get(parentNode.val)){
                parentNode.left = new TreeNode(childVal);
                stack.push(parentNode.left);
            }else {
                //找到离右子节点最近的根节点
                while (!stack.isEmpty() && inorder[inorderIndex]==stack.peek().val){
                    parentNode = stack.pop();
                    inorderIndex++;
                }
                parentNode.right = new TreeNode(childVal);
                stack.push(parentNode.right);
            }
        }
        return root;
    }

    private int[] preorder;
    private int rootIndex=0;
    private Map<Integer, Integer> idMap = new HashMap<>();
    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i =0; i<inorder.length; i++){
            idMap.put(inorder[i], i);
        }
        return buildTree1(0, inorder.length-1);

    }
    public TreeNode buildTree1(int left, int right){
        if(left>right){return null;}

        int rootVal = preorder[rootIndex];
        rootIndex++;
        TreeNode root = new TreeNode(rootVal);
        int mid = idMap.get(rootVal);
        root.left = buildTree1(left, mid-1);
        root.right = buildTree1(mid+1, right);
        return root;
    }
}
